package leetcode.editor.day;

import java.util.Arrays;

// 646. 最长数对链
// https://leetcode.cn/problems/maximum-length-of-pair-chain/
class MaximumLengthOfPairChain {
    public static void main(String[] args) {
        Solution solution = new MaximumLengthOfPairChain().new Solution();
        solution.findLongestChain(new int[][]{{1, 2}, {7, 8}, {4, 5}});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 和435.无重叠区间一致思路：https://www.programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html#%E6%80%9D%E8%B7%AF
        // 按照右边界排序
        // 贪心
        /*public int findLongestChain(int[][] pairs) {
            Arrays.sort(pairs, (o1, o2) -> o1[1] - o2[1]);
            int res = 1, right = pairs[0][1];
            for (int i = 1; i < pairs.length; i++) {
                if (pairs[i][0] > right) {
                    res++;
                    right = pairs[i][1];
                }
            }

            return res;
        }*/

        // dp
        // https://leetcode.cn/problems/maximum-length-of-pair-chain/solution/zui-chang-shu-dui-lian-by-leetcode-solut-ifpn/
        public int findLongestChain(int[][] pairs) {
            int m = pairs.length, res = 0;
            int[] dp = new int[m];
            Arrays.fill(dp, 1);
            for (int i = 1; i < m; i++) {
                for (int j = 0; j < i; j++) {
                    if (pairs[j][1] < pairs[i][0]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                    res = Math.max(dp[i], res);
                }
            }
            return res;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)
}

